package 比特教务管理系统.双链表;

import java.util.HashSet;
import java.util.Set;

public class 第四题 {

    /**
     * 输入两个链表，找出它们的第一个公共结点
     * @param myDoubleLinkedList1
     * @param myDoubleLinkedList2
     * @return
     */
    public static MyDoubleLinkedList.Node 公共结点(MyDoubleLinkedList myDoubleLinkedList1, MyDoubleLinkedList myDoubleLinkedList2){
        Set<MyDoubleLinkedList.Node> set1 = new HashSet<>();
        MyDoubleLinkedList.Node current1 = myDoubleLinkedList1.getHead();
        MyDoubleLinkedList.Node current2 = myDoubleLinkedList2.getHead();

        while(current1 != null){
            set1.add(current1);
            current1 = current1.next;
        }
        while (!set1.contains(current2)&&current2 != null){
            current2 = current2.next;
        }
        if (current2!=null) return current2;
        else return null;
    }

    public static void main(String[] args) {
        MyDoubleLinkedList myDoubleLinkedList1 = new MyDoubleLinkedList();
        MyDoubleLinkedList myDoubleLinkedList2 = new MyDoubleLinkedList();
        myDoubleLinkedList1.insertLast(1);
        myDoubleLinkedList1.insertLast(2);
        myDoubleLinkedList1.insertLast(3);
        myDoubleLinkedList2.insertLast(4);
        myDoubleLinkedList2.insertLast(5);
        myDoubleLinkedList2.insertLast(6);
        System.out.println(公共结点(myDoubleLinkedList1,myDoubleLinkedList2));
    }
}
